This invention relates to generating an optimized solution for a process under a set of constraints.
Processes are found in all industries. Various examples of the processes in manufacturing organizations include but are not limited to planning, scheduling, and the manufacture of products on an assembly line. These processes have to be optimized to attain business advantage in terms of cost and efficiency in execution. Further, these processes are usually complex, and depend on a large number of factors such as variable capacities of equipment, multiple stages of manufacture, production of several kinds of products using a single resource, manpower or process limitations, and other factors specific to the manufacturing unit. In other words, there can be a large number of rules/constraints that govern the execution of such processes. A violation of any rule or constraint directly translates into increased operational costs. Therefore, it is important to optimize such processes by adhering to all constraints of the environment.
Conventional techniques for generating the optimized solution for the process include manual and automated optimization methods. Manual optimization methods require human intervention. Further, the degree of optimization obtained in manual methods largely depends on the skills and experience of the person involved, as well as the complexity of the process involved. Furthermore, manual techniques are also time-consuming, cumbersome, and error-prone and result in poor solution quality. Further, manual techniques fail when the process to be optimized increases in size and has a large number of constraints.
Automated techniques utilize a defined algorithm to solve the optimization problem associated with a process. A general class of automated methods for optimization is based on the concept of Local Search (LS) heuristics. This technique covers a range of combinatorial heuristics, such as simulated annealing, genetic algorithm, taboo search and evolutionary algorithms.
One such heuristic is provided in the reference titled “Facts, Conjectures and Improvements for Simulated Annealing”, authored by P. Salamon, P. Sibani and R. Frost and published by SIAM Monograph in the year 2002. Another such heuristic is provided in the reference titled “Genetic Algorithms and Engineering Design”, authored by M. Gen and R. Chang, and published by John Wiley & Sons in the year 1997. Yet another heuristic is provided in the reference titled “Modern Heuristic Techniques for Combinatorial Problems”, authored by Colin Reeves and published by Halsted Press in the year 1993.
Typically, the LS technique generates the optimized solution by making local moves in the space of solutions. In all LS heuristics, an initial set of one or more solutions is generated by a convenient mechanism. Any convenient mechanism can be used because the initial set of solutions need not satisfy any constraints; they can therefore even be generated randomly. LS heuristics systematically refine the set of solutions by making small or local changes. This results in a new set of candidate solutions. The technique for generating these local changes varies according to the LS heuristic used. The set of candidate solutions is then evaluated to determine violations of the existing constraints. Based on an acceptance criterion that varies according to the heuristic used, one or more of the candidate solutions are accepted. This process is repeated until the candidate solutions do not improve appreciably, or a computational budget is exceeded. In practice, obtaining a high-quality solution requires a large number of moves, and the practical utility of the LS heuristic rests on the efficient evaluation of a large number of candidate solutions (of the order of 106 to 108) against numerous constraints.
Conventionally, candidate solutions are evaluated in their entirety. This requires high-speed computers with large storage capacities, and the optimization may not run to completion in the available time. If the evaluation is carried out incrementally (i.e., only in the neighborhoods in which the solution has changed), the method in the current state of the art is specific to a particular constraint and depends on the manner in which the local moves are generated. Thus, if there are K constraint types and L schemes for move generation, there is a need to develop K*L algorithms, along with commensurate software design, development, testing and maintenance effort. Thus, this approach requires extensive software development which is not cost effective and also time consuming. Therefore, it is evident that prolonged computational times and high expenses hinder/limit the practical use of LS heuristics.
Further, in many manufacturing processes it is desired that certain production rules/constraints are applied over certain time intervals, and not over others. Similarly, certain constraints are applicable only to a particular model of an automobile or to a particular assembly line. Currently, the optimization techniques, both manual and automated, fail to optimize a process by selective application of the constraints.
Accordingly, there is a need for a method that speeds up the computational process, along with providing efficient solutions to the processes without any manual intervention. Such method should be cost-effective, error-free, and should be easily implemented on workstations and PCs. Further, the method should selectively apply constraints to generate the optimized solution.